package com.hy;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:统计完全二叉树节点个数
 * author: Mr.Du
 * Date: 2022/11/13
 * Time: 9:14
 */
public class CountNodes {
    
    /**
     * 递归统计，前中后序遍历都可以
     * @param root
     * @return
     */
    public int countNodesByRecursive(TreeNode root) {
        if(root == null) return 0;
        return 1 + countNodesByRecursive(root.left) + countNodesByRecursive(root.right);
    }
    
    /**
     * 通过层序遍历
     * @param root
     * @return
     */
    public int countNodesByLevelOrder(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i < size;i++){
                TreeNode tmp = queue.poll();
                res++;
                if(tmp.left != null) queue.offer(tmp.left);
                if(tmp.right != null) queue.offer(tmp.right);
            }
        }
        return res;
    }
    
    /**
     * 上述两个法子都是O(n)时间复杂度
     * 下面这个方法利用完全二叉树性质来解决，
     * 满二叉树也是一个完全二叉树的一种，那么此题有两种可能，给的树就是一颗满二叉树，直接按照公式计算即可
     * 第二种最后一层节点数没有满，总体就是判断当前节点引导的子树是不是满二叉，是的话可以直接返回子树结点数，
     * 不是的话就往下遍历。由于完全二叉树的性质，左右子树中最多只有一个子树不是满二叉。
     * 所以总体的时间复杂度仍然是logn ^ 2
     * @param root
     * @return
     */
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode l = root,r = root;
        int l1 = 0,r1 = 0;
        while(l != null){
            l = l.left;
            l1++;
        }
        while(r != null){
            r = r.right;
            r1++;
        }
        if(r1 == l1){
            return (int)Math.pow(2, l1) - 1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
